import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    //直接插入排序
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//tmp中存入当前的i下标的值
            int j = i-1;//定义一个j，遍历的时候，永远跟在i下标的后边
            for (; j>=0; j--) {
                if(array[j]>tmp){//如果j下标位置的值，比tmp大
                    array[j+1]=array[j];//将j位置的值，向前挪放到i的位置，也就是j+1的位置
                }else{
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;//表示循环结束之后还有将tmp中的值付给j+1的位置。
        }
    }
    //希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;//用gap定义分组的组数
        while(gap > 1){//当组数大于1时，进入循环
            shell(array,gap);//shell方法写在前面，那么进入循环之后，先将数组分为数组元素个数的组数
            gap /= 2;
        }
        shell(array,1);//当gap等于1的时候不能进入循环，所以要将分组个数为1的情况，写在循环外，最后将数组整体排序。
    }
    //插入排序 gap为分组个数，分几组，每组之间的元素间隔为分的组数gap
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {//i从gap下标开始，向前依次遍历
            int tmp = array[i];//tmp中存入当前的i下标的值
            int j = i-gap;//定义一个j，遍历的时候，j下标永远指向同组i下标数组的后一位
            for (; j>=0; j-=gap) {//将i下标所指的数据与j下标所指数据相比，j遍历同组数据的时候，向后挪动gap个元素个数
                if(array[j]>tmp){//如果j下标位置的值，比tmp大
                    array[j+gap]=array[j];//将j位置的值，向前挪放到i的位置，也就是j+1的位置
                }else{
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;//表示循环结束之后还有将tmp中的值付给j+gap的位置。
        }
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {//i下标指向数组中已排序序列的最后一个元素
            int minIndex = i;//假定i下标所指的为最小的值
            int j = i+1;//j指向i+1的位置
            for (; j < array.length; j++) {
                if(array[minIndex]>array[j]) {//当未排序序列当中的值，于i下标的值进行比较，将较小值的下标传给minIndex
                    minIndex = j;
                }
            }
            swap(array,i,j);//当j将未排序序列的数组遍历完成之后，记录下最小的值的结点，将其于i下标的值进行交换
        }
    }
    //交换位置
    private static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //直接选择排序
    public static void selectSort2(int[] array){
        int left = 0;//定义两个指针，指向未排序数组的最开始和结尾
        int right = array.length;
        while(left < right){
            int minIndex = left;//未排序数组的最开始，minIndex与maxIndex同时指向left
            int maxIndex = left;
            for (int i = left+1; i < right; i++) {
                if(array[i]>array[maxIndex]){//判断未排序数列的i下标位置比maxIndex(最大值)下标的值大，将i赋给maxIndex
                    maxIndex = i;
                }
                if(array[i]<array[minIndex]){//判断未排序数列的i下标值比minIndex(最小值)下标的值小，将i赋给minIndex
                    minIndex = i;
                }
            }
            swap(array,minIndex,left);//将最小值，放在数组最前面
            if(maxIndex == left){//如果数组中未排序数列的maxIndex与left指向同一个地方，那么在上面的交换中，丢失了最大值，
                maxIndex = minIndex;//所以要将交换前最小值的下标传给maxIndex下标，将最大值找到
            }
            swap(array,maxIndex,right);//然后交换maxIndex与right所指位置的值
            left++;//left向前走
            right--;//right向后退
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        createBigHeap(array);//创建大根堆
        int end = array.length-1;//记录最后一个结点的下标，也是记录未排序数列的长度
        while(end > 0){//当end大于0，表示end不是根节点
            swap(array,0,end);//交换根结点与孩子结点的位置
            shiftDown(array,0,end);//交换完成之后，向下调整，将堆调整成新的大根堆,开始位置是0下标，结束位置是9下标，结束位置也是未排序数列的长度
            end--;//交换完成之后，最后一个结点不计算在内。
        }
    }
    //创建大根堆
    private static void createBigHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {//建立大根堆，根据求父节点的公式得，当子节点大于0时，父节点为（i-1）/2,i结点为数组长度-1
            shiftDown(array,parent,array.length);//向下调整
        }
    }
    //向下调整
    private static void shiftDown(int[] array,int parent,int len){//将数组传给这个方法，父节点下标。数组长度为len
        int child = 2*parent+1;//根据传进来得父亲结点得下标，来计算左孩子结点下标，
        while(child < len){//这里表示最起码要有左孩子结点得下标，才能进行孩子结点与父节点的比较，交换
            if (child + 1 < len && array[child] < array[child+1]) {//表示存在有孩子结点，并且左孩子小于右孩子
                child++;//孩子结点挪到右孩子结点处，记录右孩子结点
            }
            //若没有右孩子，则直接左孩子与父节点比较
            //若存在右孩子节点，但是比左孩子结点小，那么不进入上边的判断，child记录的就是最大的孩子结点，直接与父亲结点比较
            if(array[child] > array[parent]){//孩子结点比夫妻节点大
                swap(array,child,parent);//交换
                parent = child;//父节点指向孩子结点，作为新的父节点，进行上述操作
                child = 2*parent+1;//孩子结点，重新计算结点下标，这样就实现了向下调整的操作
            }else{//如果孩子结点没有父亲结点大，那么就直接结束，不需要调整
                break;
            }
        }
    }
    //冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {//冒泡排序的趟数
            boolean flg = false;//记录有没有在进行比较
            //一趟冒泡排序
            for (int j = 0; j < array.length-1-i; j++) {//array.length-1-i表示的是，每进行完一趟，相应的比较次数少i次
                if (array[j] > array[j+1]){//如果j下标的数据大于j+1下标的数据，则交换
                    swap(array,j,j+1);
                    flg = true;//满足条件，交换之后，flg变为true
                }
            }
            //当在某趟比较的时候j下标的值，比j+1下标的值小，这一趟中没有进行交换，那么表示数组已排序完成，没有必要在进行下一趟比较了
            if(flg == false){//flg==false表示j下标的值比j+1位置的值小，排序已完成，
                return;
            }
        }
    }


    //快速排序
    public static void quickSort(int[] array){
        quick1(array,0,array.length-1);//传给quick方法 数组 0下标 数组结尾下标
    }
    //划分
    public static void quick(int[] array,int start,int end){//start指向数组的0下标，end指向数组的结尾
        if(start >= end){//倘若start所指的下标大于等于end所指的下标
            return;//则递归结束
        }
        int pivot = partition(array,start,end);//用pivot指向基准值，基准值为start与end共同指向的位置的值
        //递归基准值的左边
        quick(array,start,pivot-1);//在quick当前这个方法中，start指向0下标，找到基准值之后，0下标位置为start，结尾下标为基准值的前一位
        //递归基准值的右边
        quick(array,pivot+1,end);//在quick当前这个方法中，end指向数组的结尾，所以递归基准值的右边的时候，开始位置为pivot+1的位置
    }
    //挖坑法(找基准并且排序)
    private static int partition(int[] array,int left,int right){//接收传过来的数组，并用left指向数组的最开始，right指向数组的结尾
        int tmp = array[left];//以数组的0下标的值作为标准
       while(left < right){//这层循环确保left和right两个指针将数组遍历完
           //让right下标的值与tmp中的值比较，right的值大，则right向前移动，若right的值小，则不进入循环，将right所指的值放在left所指的位置，找到比tmp小的值，right就会停止移动
            while(left < right && array[right] >= tmp){//这里要确保right不能越界，当right所指的值，一直都比tmp大时，right一直向前挪动，最后会指向-1，就会发生越界，那么就要right不能小于等于left
                right--;
            }
            array[left] = array[right];
            //让left下标的值与tmp比较，left的值比tmp的小，则一直向前挪动，直到left指向的值比tmp的值大，不进入循环，将left所指的值，放入刚刚right的位置，
            while(left < right && array[left] <= tmp){//这里要确保left不会越界，就要在设置一个条件就是left的下标位置不能大于等于right的下标，否则就会发生越界
                left++;
            }
           array[right] = array[left];
        }
       //当left和right相遇不进入循环，将tmp的值，放在最后一个坑中，无论是将tmp中的值，给left所指的位置还是right所指的位置都一样
        array[left] = tmp;
        return left;//基准值就是left与right相遇的位置，将其返回给方法的调用者
    }
    //Hoare版（找基准并排序）
    private static int partition2(int[] array,int left,int right) {
        int tmp = array[left];
        int i = left;//用i记录基准值的下标，方便下边的left和right相遇时，交换基准值的位置
        while(left<right){
            while(left < right && array[right] >= tmp){//遍历到的值比tmp大，进入循环，将right向前移动一位；若是找到比tmp小的不进入循环，停止，right将这个值记录
                right--;
            }
            while(left < right && array[left] <= tmp){//遍历到的值比tmp小，进入循环，将left向后移动一位；若找到比tmp大的不进入循环，停止，left将这个值记录
                left++;
            }
            swap(array,left,right);//然后将left和right记录的下标传给交换函数，将比基准值大的放在后面，比基准值小的放在前面
        }
        //当left和right指针相遇，则交换基准值和两指针指向的位置的值
        swap(array,left,i);//当两个指针相遇，不论那谁和i交换值都可以
        return left;//基准值就是left与right相遇的位置，将其返回给方法的调用者
    }
    private static int  partition3(int[] array,int left,int right){
        int prev = left;
        int cur = left+1;
        while(cur <= right){//遍历当cur超过数组范围时，结束循环
            if(array[cur] < array[left] && array[++prev] != array[cur]){//如果cur遍历到的值小于基准值时，prev先向前移动一位，再判断prev与cur是否相遇，或者两个指针所指的值是否相等
                swap(array,cur,prev);//若cur值小于基准值并且cur和prev没有相遇,两个指针所指的值不相等，则进入进行交换
            }
            //否则，cur向前移动
            cur++;
        }
        //循环结束后，交换prev和基准值的位置
        swap(array,prev,left);
        return prev;//最终返回基准值的位置
    }
    //划分
    public static void quick1(int[] array,int start,int end){//start指向数组的0下标，end指向数组的结尾
        if(start >= end){//倘若start所指的下标大于等于end所指的下标
            return;//则递归结束
        }
        //三数取中法
        int index = midThree(array,start,end);//找到三个数中，中间大小的值
        swap(array,index,start);//交换中间大小的值，到数组的起始位置，作为基准值

        int pivot = partition(array,start,end);//用pivot指向基准值，基准值为start与end共同指向的位置的值
        //递归基准值的左边
        quick(array,start,pivot-1);//在quick当前这个方法中，start指向0下标，找到基准值之后，0下标位置为start，结尾下标为基准值的前一位
        //递归基准值的右边
        quick(array,pivot+1,end);//在quick当前这个方法中，end指向数组的结尾，所以递归基准值的右边的时候，开始位置为pivot+1的位置
    }
    private static int midThree(int[] array,int left,int right){
        int mid = (left+right)/2;//找到中间位置
        //判断left、right和mid所指的三个值的大小，中间大小的作为基准值
        if(left < right){//当right大于left的情况
            //下边的判断条件不能发生变换，要用前两个判断条件约束最后一个else
            if(array[left]>array[mid]){
                return left;//中间位置为left下标的值
            }else if(array[right]<array[mid]){
                return right;//中间位置为right下标的值
            }else{
                return mid;//最后mid的值不大于right也不小于left,为中间的值
            }
        }else{//当left大于right的情况
            if(array[left]<array[mid]){
                return left;
            }else if(array[right]>array[mid]){
                return right;
            }else{
                return mid;
            }
        }
    }
    //划分
    public static void quick3(int[] array,int start,int end){//start指向数组的0下标，end指向数组的结尾
        if(start >= end){//倘若start所指的下标大于等于end所指的下标
            return;//则递归结束
        }
        if((end-start+1)<= 14){//这里用子数组结束位置下标-开始位置下标+1：表示子数组的元素个数
            //调用直接插入排序
            insertSort1(array,start,end);//传给直接插入排序子数组，开始位置，和结束位置（区间）
            return;//满足条件进入之后，用直接插入排序排完之后，不会再向下递归了。
        }

        int pivot = partition(array,start,end);//用pivot指向基准值，基准值为start与end共同指向的位置的值
        //递归基准值的左边
        quick(array,start,pivot-1);//在quick当前这个方法中，start指向0下标，找到基准值之后，0下标位置为start，结尾下标为基准值的前一位
        //递归基准值的右边
        quick(array,pivot+1,end);//在quick当前这个方法中，end指向数组的结尾，所以递归基准值的右边的时候，开始位置为pivot+1的位置
    }
    private static void insertSort1(int[] array,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];//tmp中存入当前的i下标的值
            int j = i-1;//定义一个j，遍历的时候，永远跟在i下标的后边
            for (; j>=left; j--) {
                if(array[j]>tmp){//如果j下标位置的值，比tmp大
                    array[j+1]=array[j];//将j位置的值，向前挪放到i的位置，也就是j+1的位置
                }else{
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;//表示循环结束之后还有将tmp中的值付给j+1的位置。
        }
    }
    public static void quickSort2(int[] array){
        Deque<Integer> stack = new LinkedList<>();//示例化一个栈
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);//第一次找基准值
        if(pivot > left+1){//找到的基准值左侧最起码要有两个值
            stack.push(left);
            stack.push(pivot-1);//将基准值左侧的一个数据作为左侧结束位置
        }
        if (pivot < right - 1){//找到的基准值右侧最起码要有两个值
            stack.push(pivot+1);//将基准值右侧的一个数据作为右侧开始位置
            stack.push(right);
        }
        //到这里，栈中已经存在4个数据了
        while(!stack.isEmpty()){//以栈为空作为结束条件
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot < right - 1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }
    //分割
    private static void mergeSortFunc(int[] array,int left,int right){
        if (left >= right){
            return;
        }
        int mid = (left+right)/2;//找出每次数组的中间位置
        //分割中间位置左边的子数组
        mergeSortFunc(array,left,mid);//将数组传给这个方法，在栈上开辟空间，将栈上的数组进行分割
        mergeSortFunc(array,mid+1,right);
        //将数组的左右子数组都分割完之后，合并
        merge(array,left,right,mid);//将本层对应的中间值传给merge方法，在merge方法中用来确定两个子序列的开始位置，和结束位置
    }
    //合并
    private static void merge(int[] array,int start,int end,int mid){
        int s1 = start;//数组的开始位置和结束位置不动，用两个变量来变量数组
        //int e1 = mid;
        int s2 = mid+1;
        //int e2 = end;
        int[] tmp = new int[end - start + 1];//定义一个与每层相同长度的数组
        int k = 0;//表示tmp数组的下标，添加一个元素+1
        //s1 = mid时，数组中只有一个元素或者是在排序的时候s1向前挪动，走到了end位置，s2同理
        while(s1 <= mid && s2 <= end){
            if(array[s1] <= array[s2]){//s1和s2进行比较，s1的值小，放入tmp中，tmp中记录数组下标的k向前移动，s1也想前移动
                tmp[k++] = array[s1++];
            }else{//如果s2小，s2放入tmp数组中
                tmp[k++] = array[s2++];
            }
        }
        //通过比较，若一个数组s1中的元素较小，一个s2中的较大，刚好s1全部已经放完，那么就将s2中的剩余元素依次放入tmp数组中
        while(s1 <= mid){//表示s1数组中有剩余元素
            tmp[k++] = array[s1++];
        }
        while(s2 <= end){//表示s2数组中有剩余元素
            tmp[k++] = array[s2++];
        }
        //当将所有的元素都放入tmp数组中，将tmp中的数组元素拷贝到递归本层的原数组中
        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];//分割的时候，中间值右边的子数组，开始位置并不是从0下标开始的，所以我们要从start的位置开始拷贝
        }
    }
    //非递归实现归并排序
    public static void mergeSort1(int[] array){
        int gap = 1;//认为传给这个方法的数组每个元素都是一个整体，每个整体都有一个元素。
        while(gap < array.length){//当gap等于数组长度时，数组已经有序，循环结束
            for (int i = 0; i < array.length; i += gap*2) {//两两一组，进行合并，一组合并完成之后，i向后移动gap*2的长度
                int left = i;//left跟随i指向每组合并的两个元素的开始位置
                int mid = left+gap-1;
                if(mid >= array.length){//如果mid越界，这里就需要修正一下，让mid指向数组的最后一位
                    mid = array.length-1;
                }
                int right = mid+gap;
                if(right >= array.length){//同样的right也要防止越界，若越界之后，要将其修正回来
                    right= array.length-1;
                }

                merge(array,left,right,mid);
            }
            gap *= 2;//每层交换完成之后，每组之中元素个数乘2。
        }
    }
}

